In a communication network, a user may establish connections between a source node and a destination node via a flow of data transferred over one or more network paths. A group of two or more flows, or member flows, is referred to as a flow aggregate. The flow aggregate may be defined based on any suitable attribute of its member flows, such as the location of the corresponding source nodes or destination nodes, associated users, data type, and/or associated applications. For example, a flow aggregate may include all or a subset of all flows for a particular user between Europe and North America, all or a subset of all flows destined into or originating from a particular metropolitan area for a particular user, all or a subset of all flows associated with a particular application or product area, and all or a subset of all flows belonging to a group of users.
A flow may have a utility function U that maps between a performance measure u of the flow and a service s delivered by the network. The quantity s contains one or more measures of service delivered to the flow, for example, the amount of resources delivered to the flow such as bandwidth, delay and/or loss ratio. The quantity u may be based on a flow-level, user-level, and/or application-layer assessment, for example, the perceptual quality of a video stream or the speed of a file transfer.
Flows may have different utility functions. For example, some flows used by data applications such as electronic mail and file transfer may be relatively tolerant of end-to-end delays. The utility functions of these flows can be modeled using a continuous, diminishing-return (logarithmic) utility function such as utility function 22 of FIG. 1A (where U(s)=log s). In contrast, some flows, such as ones associated with real-time applications, are highly sensitive to delay and can experience severe performance degradation if the flows do not receive sufficient resources, such as bandwidth. The utility functions of such flows may be modeled using a nearly single step utility function such as utility function 21 of FIG. 1A. Yet other flows may have a best effort (linear) utility function such as utility function 23 of FIG. 1A, where utility linearly increases with assigned bandwidth according to one utility weight w (U(s)=w*s). Other flows may have utility functions that increase linearly but discontinuously, i.e., according to utility weights that vary as the available bandwidth changes. In these cases, utility may be modeled using a piecewise linear function such as utility function 24 of FIG. 1A.
The allocation of shared resources to different flows of a network is a fundamental problem in distributed computing and networking. A well accepted principle is that network resources belong to all flows and thus should be shared among the flows in a fair and non-discriminatory way. Various fairness criteria can be used.
In one fair allocation strategy, known as bandwidth max-min fairness, resources are allocated among individual flows to be max-min fair. According to this strategy, network resources are assigned to individual flows in order of increasing demand. This strategy attempts to maximize the minimum resources received by any individual flow sharing the network. This strategy, however, does not take into account the utility or benefit to each flow from the allocated resources.
In another fair allocation strategy, known as utility max-min fairness, resources are allocated among individual flows so that flow utilities from the allocated resources are max-min fair. This strategy attempts to maximize the minimum utility received by any individual flow sharing the network.
These bandwidth and utility max-min fairness strategies aim to achieve fairness at the flow level, by performing max-min fair allocation of either utility or bandwidth for each flow. These strategies, however, do not apply fairness at different levels of flow aggregation. For example, these strategies do not achieve fairness across groups of flows, or flow aggregates. In addition, these strategies do not achieve fairness across flow aggregates that are arbitrarily defined, e.g., across flow aggregates that include flows with different source nodes or destination nodes, or across flow aggregates that include flows used by particular applications or by particular groups of users.